home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / lr0.c < prev    next >
C/C++ Source or Header  |  1990-07-14  |  10KB  |  605 lines
  1. #include "defs.h"
  2.  
  3. extern short *itemset;
  4. extern short *itemsetend;
  5. extern unsigned *ruleset;
  6.  
  7. int nstates;
  8. core *first_state;
  9. shifts *first_shift;
  10. reductions *first_reduction;
  11.  
  12. int get_state();
  13. core *new_state();
  14.  
  15. static core **state_set;
  16. static core *this_state;
  17. static core *last_state;
  18. static shifts *last_shift;
  19. static reductions *last_reduction;
  20.  
  21. static int nshifts;
  22. static short *shift_symbol;
  23.  
  24. static short *redset;
  25. static short *shiftset;
  26.  
  27. static short **kernel_base;
  28. static short **kernel_end;
  29. static short *kernel_items;
  30.  
  31.  
  32. allocate_itemsets()
  33. {
  34.   register short *itemp;
  35.   register short *item_end;
  36.   register int symbol;
  37.   register int i;
  38.   register int count;
  39.   register int max;
  40.   register short *symbol_count;
  41.  
  42.   count = 0;
  43.   symbol_count = NEW2(nsyms, short);
  44.  
  45.   item_end = ritem + nitems;
  46.   for (itemp = ritem; itemp < item_end; itemp++)
  47.     {
  48.       symbol = *itemp;
  49.       if (symbol >= 0)
  50.     {
  51.       count++;
  52.       symbol_count[symbol]++;
  53.     }
  54.     }
  55.  
  56.   kernel_base = NEW2(nsyms, short *);
  57.   kernel_items = NEW2(count, short);
  58.  
  59.   count = 0;
  60.   max = 0;
  61.   for (i = 0; i < nsyms; i++)
  62.     {
  63.       kernel_base[i] = kernel_items + count;
  64.       count += symbol_count[i];
  65.       if (max < symbol_count[i])
  66.     max = symbol_count[i];
  67.     }
  68.  
  69.   shift_symbol = symbol_count;
  70.   kernel_end = NEW2(nsyms, short *);
  71. }
  72.  
  73.  
  74.  
  75. allocate_storage()
  76. {
  77.   allocate_itemsets();
  78.  
  79.   shiftset = NEW2(nsyms, short);
  80.   redset = NEW2(nrules + 1, short);
  81.   state_set = NEW2(nitems, core *);
  82. }
  83.  
  84.  
  85.  
  86. append_states()
  87. {
  88.   register int i;
  89.   register int j;
  90.   register int symbol;
  91.  
  92. #ifdef    TRACE
  93.   fprintf(stderr, "Entering append_states\n");
  94. #endif
  95.  
  96.   for (i = 1; i < nshifts; i++)
  97.     {
  98.       symbol = shift_symbol[i];
  99.       j = i;
  100.       while (j > 0 && shift_symbol[j - 1] > symbol)
  101.     {
  102.       shift_symbol[j] = shift_symbol[j - 1];
  103.       j--;
  104.     }
  105.       shift_symbol[j] = symbol;
  106.     }
  107.  
  108.   for (i = 0; i < nshifts; i++)
  109.     {
  110.       symbol = shift_symbol[i];
  111.       shiftset[i] = get_state(symbol);
  112.     }
  113. }
  114.  
  115.  
  116. free_storage()
  117. {
  118.   FREE(shift_symbol);
  119.   FREE(redset);
  120.   FREE(shiftset);
  121.   FREE(kernel_base);
  122.   FREE(kernel_end);
  123.   FREE(kernel_items);
  124.   FREE(state_set);
  125. }
  126.  
  127.  
  128.  
  129. generate_states()
  130. {
  131.   allocate_storage();
  132.   itemset = NEW2(nitems, short);
  133.   ruleset = NEW2(WORDSIZE(nrules), unsigned);
  134.   set_first_derives();
  135.   initialize_states();
  136.  
  137.   while (this_state)
  138.     {
  139.       closure(this_state->items, this_state->nitems);
  140.       save_reductions();
  141.       new_itemsets();
  142.       append_states();
  143.  
  144.       if (nshifts > 0)
  145.         save_shifts();
  146.  
  147.       this_state = this_state->next;
  148.     }
  149.  
  150.   finalize_closure();
  151.   free_storage();
  152. }
  153.  
  154.  
  155.  
  156. int
  157. get_state(symbol)
  158. int symbol;
  159. {
  160.   register int key;
  161.   register short *isp1;
  162.   register short *isp2;
  163.   register short *iend;
  164.   register core *sp;
  165.   register int found;
  166.  
  167.   int n;
  168.  
  169. #ifdef    TRACE
  170.   fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
  171. #endif
  172.  
  173.   isp1 = kernel_base[symbol];
  174.   iend = kernel_end[symbol];
  175.   n = iend - isp1;
  176.  
  177.   key = *isp1;
  178.   assert(0 <= key && key < nitems);
  179.   sp = state_set[key];
  180.   if (sp)
  181.     {
  182.       found = 0;
  183.       while (!found)
  184.     {
  185.       if (sp->nitems == n)
  186.         {
  187.           found = 1;
  188.           isp1 = kernel_base[symbol];
  189.           isp2 = sp->items;
  190.  
  191.           while (found && isp1 < iend)
  192.         {
  193.           if (*isp1++ != *isp2++)
  194.             found = 0;
  195.         }
  196.         }
  197.  
  198.       if (!found)
  199.         {
  200.           if (sp->link)
  201.         {
  202.           sp = sp->link;
  203.         }
  204.           else
  205.         {
  206.           sp = sp->link = new_state(symbol);
  207.           found = 1;
  208.         }
  209.         }
  210.     }
  211.     }
  212.   else
  213.     {
  214.       state_set[key] = sp = new_state(symbol);
  215.     }
  216.  
  217.   return (sp->number);
  218. }
  219.  
  220.  
  221.  
  222. initialize_states()
  223. {
  224.     register int i;
  225.     register short *start_derives;
  226.     register core *p;
  227.  
  228.     start_derives = derives[start_symbol];
  229.     for (i = 0; start_derives[i] >= 0; ++i)
  230.     continue;
  231.  
  232.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  233.     if (p == 0) no_space();
  234.  
  235.     p->next = 0;
  236.     p->link = 0;
  237.     p->number = 0;
  238.     p->accessing_symbol = 0;
  239.     p->nitems = i;
  240.  
  241.     for (i = 0;  start_derives[i] >= 0; ++i)
  242.     p->items[i] = rrhs[start_derives[i]];
  243.  
  244.     first_state = last_state = this_state = p;
  245.     nstates = 1;
  246. }
  247.  
  248.  
  249. new_itemsets()
  250. {
  251.   register int i;
  252.   register int shiftcount;
  253.   register short *isp;
  254.   register short *ksp;
  255.   register int symbol;
  256.  
  257.   for (i = 0; i < nsyms; i++)
  258.     kernel_end[i] = 0;
  259.  
  260.   shiftcount = 0;
  261.   isp = itemset;
  262.   while (isp < itemsetend)
  263.     {
  264.       i = *isp++;
  265.       symbol = ritem[i];
  266.       if (symbol > 0)
  267.     {
  268.           ksp = kernel_end[symbol];
  269.  
  270.           if (!ksp)
  271.         {
  272.           shift_symbol[shiftcount++] = symbol;
  273.           ksp = kernel_base[symbol];
  274.         }
  275.  
  276.           *ksp++ = i + 1;
  277.           kernel_end[symbol] = ksp;
  278.     }
  279.     }
  280.  
  281.   nshifts = shiftcount;
  282. }
  283.  
  284.  
  285.  
  286. core *
  287. new_state(symbol)
  288. int symbol;
  289. {
  290.   register int n;
  291.   register core *p;
  292.   register short *isp1;
  293.   register short *isp2;
  294.   register short *iend;
  295.  
  296. #ifdef    TRACE
  297.   fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
  298. #endif
  299.  
  300.   if (nstates >= MAXSHORT)
  301.     fatal("too many states");
  302.  
  303.   isp1 = kernel_base[symbol];
  304.   iend = kernel_end[symbol];
  305.   n = iend - isp1;
  306.  
  307.   p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  308.   p->accessing_symbol = symbol;
  309.   p->number = nstates;
  310.   p->nitems = n;
  311.  
  312.   isp2 = p->items;
  313.   while (isp1 < iend)
  314.     *isp2++ = *isp1++;
  315.  
  316.   last_state->next = p;
  317.   last_state = p;
  318.  
  319.   nstates++;
  320.  
  321.   return (p);
  322. }
  323.  
  324.  
  325. /* show_cores is used for debugging */
  326.  
  327. show_cores()
  328. {
  329.     core *p;
  330.     int i, j, k, n;
  331.     int itemno;
  332.  
  333.     k = 0;
  334.     for (p = first_state; p; ++k, p = p->next)
  335.     {
  336.     if (k) printf("\n");
  337.     printf("state %d, number = %d, accessing symbol = %s\n",
  338.         k, p->number, symbol_name[p->accessing_symbol]);
  339.     n = p->nitems;
  340.     for (i = 0; i < n; ++i)
  341.     {
  342.         itemno = p->items[i];
  343.         printf("%4d  ", itemno);
  344.         j = itemno;
  345.         while (ritem[j] >= 0) ++j;
  346.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  347.         j = rrhs[-ritem[j]];
  348.         while (j < itemno)
  349.         printf(" %s", symbol_name[ritem[j++]]);
  350.         printf(" .");
  351.         while (ritem[j] >= 0)
  352.         printf(" %s", symbol_name[ritem[j++]]);
  353.         printf("\n");
  354.         fflush(stdout);
  355.     }
  356.     }
  357. }
  358.  
  359.  
  360. /* show_ritems is used for debugging */
  361.  
  362. show_ritems()
  363. {
  364.     int i;
  365.  
  366.     for (i = 0; i < nitems; ++i)
  367.     printf("ritem[%d] = %d\n", i, ritem[i]);
  368. }
  369.  
  370.  
  371. /* show_rrhs is used for debugging */
  372. show_rrhs()
  373. {
  374.     int i;
  375.  
  376.     for (i = 0; i < nrules; ++i)
  377.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  378. }
  379.  
  380.  
  381. /* show_shifts is used for debugging */
  382.  
  383. show_shifts()
  384. {
  385.     shifts *p;
  386.     int i, j, k;
  387.  
  388.     k = 0;
  389.     for (p = first_shift; p; ++k, p = p->next)
  390.     {
  391.     if (k) printf("\n");
  392.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  393.         p->nshifts);
  394.     j = p->nshifts;
  395.     for (i = 0; i < j; ++i)
  396.         printf("\t%d\n", p->shift[i]);
  397.     }
  398. }
  399.  
  400.  
  401. save_shifts()
  402. {
  403.   register shifts *p;
  404.   register short *sp1;
  405.   register short *sp2;
  406.   register short *send;
  407.  
  408.   p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  409.             (nshifts - 1) * sizeof(short)));
  410.  
  411.   p->number = this_state->number;
  412.   p->nshifts = nshifts;
  413.  
  414.   sp1 = shiftset;
  415.   sp2 = p->shift;
  416.   send = shiftset + nshifts;
  417.  
  418.   while (sp1 < send)
  419.     *sp2++ = *sp1++;
  420.  
  421.   if (last_shift)
  422.     {
  423.       last_shift->next = p;
  424.       last_shift = p;
  425.     }
  426.   else
  427.     {
  428.       first_shift = p;
  429.       last_shift = p;
  430.     }
  431. }
  432.  
  433.  
  434.  
  435. save_reductions()
  436. {
  437.   register short *isp;
  438.   register short *rp1;
  439.   register short *rp2;
  440.   register int item;
  441.   register int count;
  442.   register reductions *p;
  443.  
  444.   short *rend;
  445.  
  446.   count = 0;
  447.   for (isp = itemset; isp < itemsetend; isp++)
  448.     {
  449.       item = ritem[*isp];
  450.       if (item < 0)
  451.     {
  452.       redset[count++] = -item;
  453.     }
  454.     }
  455.  
  456.   if (count)
  457.     {
  458.       p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  459.                     (count - 1) * sizeof(short)));
  460.  
  461.       p->number = this_state->number;
  462.       p->nreds = count;
  463.  
  464.       rp1 = redset;
  465.       rp2 = p->rules;
  466.       rend = rp1 + count;
  467.  
  468.       while (rp1 < rend)
  469.     *rp2++ = *rp1++;
  470.  
  471.       if (last_reduction)
  472.     {
  473.       last_reduction->next = p;
  474.       last_reduction = p;
  475.     }
  476.       else
  477.     {
  478.       first_reduction = p;
  479.       last_reduction = p;
  480.     }
  481.     }
  482. }
  483.  
  484.  
  485. set_derives()
  486. {
  487.   register int i, k;
  488.   register int lhs;
  489.   register short *rules;
  490.  
  491.   derives = NEW2(nsyms, short *);
  492.   rules = NEW2(nvars + nrules, short);
  493.  
  494.   k = 0;
  495.   for (lhs = start_symbol; lhs < nsyms; lhs++)
  496.     {
  497.       derives[lhs] = rules + k;
  498.       for (i = 0; i < nrules; i++)
  499.     {
  500.       if (rlhs[i] == lhs)
  501.         {
  502.           rules[k] = i;
  503.           k++;
  504.         }
  505.     }
  506.       rules[k] = -1;
  507.       k++;
  508.     }
  509.  
  510. #ifdef    DEBUG
  511.   print_derives();
  512. #endif
  513. }
  514.  
  515. free_derives()
  516. {
  517.   FREE(derives[start_symbol]);
  518.   FREE(derives);
  519. }
  520.  
  521. #ifdef    DEBUG
  522. print_derives()
  523. {
  524.   register int i;
  525.   register short *sp;
  526.  
  527.   printf("\nDERIVES\n\n");
  528.  
  529.   for (i = start_symbol; i < nsyms; i++)
  530.     {
  531.       printf("%s derives ", symbol_name[i]);
  532.       for (sp = derives[i]; *sp >= 0; sp++)
  533.     {
  534.       printf("  %d", *sp);
  535.     }
  536.       putchar('\n');
  537.     }
  538.  
  539.   putchar('\n');
  540. }
  541. #endif
  542.  
  543.  
  544. set_nullable()
  545. {
  546.     register int i, j;
  547.     register int empty;
  548.     int done;
  549.  
  550.     nullable = MALLOC(nsyms);
  551.     if (nullable == 0) no_space();
  552.  
  553.     for (i = 0; i < nsyms; ++i)
  554.     nullable[i] = 0;
  555.  
  556.     done = 0;
  557.     while (!done)
  558.     {
  559.     done = 1;
  560.     for (i = 1; i < nitems; i++)
  561.     {
  562.         empty = 1;
  563.         while ((j = ritem[i]) >= 0)
  564.         {
  565.         if (!nullable[j])
  566.             empty = 0;
  567.         ++i;
  568.         }
  569.         if (empty)
  570.         {
  571.         j = rlhs[-j];
  572.         if (!nullable[j])
  573.         {
  574.             nullable[j] = 1;
  575.             done = 0;
  576.         }
  577.         }
  578.     }
  579.     }
  580.  
  581. #ifdef DEBUG
  582.     for (i = 0; i < nsyms; i++)
  583.     {
  584.     if (nullable[i])
  585.         printf("%s is nullable\n", symbol_name[i]);
  586.     else
  587.         printf("%s is not nullable\n", symbol_name[i]);
  588.     }
  589. #endif
  590. }
  591.  
  592.  
  593. free_nullable()
  594. {
  595.   FREE(nullable);
  596. }
  597.  
  598.  
  599. lr0()
  600. {
  601.     set_derives();
  602.     set_nullable();
  603.     generate_states();
  604. }
  605.